1. Field of the Invention
The present invention relates to methods of motion estimation in a sequence of moving video pictures. More specifically, but not exclusively, the invention relates to methods of motion vector estimation and an apparatus for the same.
2. Description of the Prior Art
A prior art motion estimation technique, called xe2x80x9c3-D Recursive Search,xe2x80x9d has been described by Gerard de Haan and P. W. A. C. Biezen, in xe2x80x9cSub-pixel motion estimation with 3-D recursive search block-matching,xe2x80x9d Signal Processing: Image Communication 6, pp. 229-239 (1994), incorporated herein by reference as if set forth in full.
3-D Recursive Search falls in the class of block-recursive motion estimators. The algorithm is based on the assumptions that motion does not change much in time, i.e., from field to field. The algorithm maintains a vector field which is updated on field basis. The vector field is usually similar for a relatively large region, i.e., for an object. Therefore the motion vectors in the neighborhood of a location are good candidates for the motion at that location.
A motion video consists of a sequence of fields. Each field is divided into blocks, e.g., of 16 by 16 pixels. A motion vector is associated with each block. The motion vector should hold the displacement between the block in the current frame compared to a previous field or next field. For example, to update the motion vector of block (x, y) in a current field, a 3-D Recursive Search uses only a limited number of candidate vectors, say five, for the estimation, namely, some vectors from the previous field, i.e., temporal vectors, some vectors from the current field, i.e., spatial vectors, and an update of a spatial vector. For each candidate the motion estimation error is calculated. The candidate with the lowest motion estimation error is chosen as the best motion vector for that block. The algorithm uses the normal raster scan order to go through the blocks.
3-D recursive search estimators are also described by G. de Haan, et al. in xe2x80x9cTrue Motion Estimation with 3-D Recursive search block matching,xe2x80x9d IEEE Trans. Circuits and Systems for Video Technology, Vol. 3, October 1993, pp. 368-379; incorporated herein by reference as set forth in full and in the previously cited xe2x80x9cSub-pixel motion estimation . . . xe2x80x9d article.
Motion estimation is useful in several applications. It is part of predictive coding applications like MPEG-2, H.263, and the like. In these applications, motion vectors are used to maximize temporal correlation, thereby minimizing coding error. Motion estimation is also used in the field of video enhancement, for example, to improve the motion portrayal of motion pictures, deinterlacing, or temporal noise reduction.
Motion can be estimated in several ways. For example, motion estimators include a full-search estimator, block-matching, object-based methods, and the like. Nevertheless, they all try to maximize temporal correlation by assuming a certain spatial-invariant motion model. As an example, the 3-D-Recursive Search motion estimator, used in the Philips Natural Motion TV sets, estimates translational motion on a block basis.
In the 3-D Recursive Search Estimator, the candidate motion vectors are selected on a per block basis. An error function, e.g., a mean squared error or mean absolute difference, is calculated per candidate. A penalty is added which depends on the candidate type, e.g., spatial or temporal. The penalty per candidate type is spatially invariant, i.e., it does not vary with the spatial position of the block. As a result, the use of this type of penalty only may result in suboptimal coding gain and some artifacts in the picture.
It is, therefore, an object of the present invention to provide an improved motion estimation method. It is another object of the invention to increase the speed of convergence of motion vectors to improve the convergence process.
The present invention, which addresses the needs of the prior art, provides an improved motion vector estimation method and a device for the same. As shown in FIG. 1, in a preferred embodiment of the invention, a motion estimator generates at least two candidate motion vectors (110) and an error function having a penalty that depends on the position and size of the candidate motion vectors is applied in order to select a best motion vector (120). Each candidate motion vector is associated with a region representation of a video image.
As shown in FIG. 2, the present invention is also a device 200 for recursive motion vector estimation having enhanced convergence including a random vector generator 210 for generating a plurality of candidate motion vectors associated with selected regions in at least a first and second video image, a best vector selector 220 for comparing the candidate motion vectors of selected regions in a first and a second video image, the best vector selector including means 222 for evaluating the candidate motion vectors by applying an error function having at least a penalty that depends on the position and size of the candidate motion vectors.
Other improvements which the present invention provides over the prior art will be identified as a result of the following description which sets forth the preferred embodiments of the present invention. The description is not in any way intended to limit the scope of the present invention, but rather only to provide the working example of the present preferred embodiments. The scope of the present invention is only limited as indicated in the appended claims.